package dp

func generate(numRows int) [][]int {
	res := make([][]int, numRows)
	if numRows == 0 {
		return res
	}
	res[0] = []int{1}
	var buildRow func(rowIdx int)
	buildRow = func(rowIdx int) {
		prevRow := res[rowIdx-1]
		currentRow := make([]int, rowIdx+1)
		currentRow[0], currentRow[rowIdx] = 1, 1

		for j := 1; j < rowIdx; j++ {
			currentRow[j] = prevRow[j-1] + prevRow[j]
		}
		res[rowIdx] = currentRow
	}

	for i := 1; i < numRows; i++ {
		buildRow(i)
	}
	return res
}

func generate2(numRows int) [][]int {
	res := make([][]int, numRows)
	for i := 0; i < numRows; i++ {
		res[i] = make([]int, i + 1)
		res[i][0], res[i][i] = 1, 1
		for j := 1; j < i;j ++ {
			res[i][j] = res[i - 1][j] + res[i - 1][j - 1]
		}
	}
	return res
}
